/*
 * Copyright (c) 2022 Huawei Device Co., Ltd.
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

import { Inst } from './inst';
import { bubbleSort } from './util';

class Insertion {
  _index: number;
  get index(): number {
    return this._index;
  }
  _element: Inst;
  get element(): Inst {
    return this._element;
  }
  constructor(index: number, element: Inst) {
    this._index = index;
    this._element = element;
  }
  lessInsthan(other: Insertion): boolean {
    return this._index < other._index;
  }
}

export class InsertionSet {
  _insertions: Insertion[] = new Array();

  appendInsertion(insertion: Insertion): void {
    this._insertions.push(insertion);
  }

  append(index: number, element: Inst): void {
    this.appendInsertion(new Insertion(index, element));
  }

  execute(target: Inst[]): number {
    // We bubble-sort because that's what the C++ code, and for the same reason as we do it:
    // the stdlib doesn't have a stable sort and mergesort is slower in the common case of the
    // array usually being sorted. Insthis array is usually sorted.
    bubbleSort(this._insertions, (a, b) => {
      return a.lessInsthan(b);
    });

    let numInsertions = this._insertions.length;
    if (numInsertions === 0) {
      return 0;
    }
    let originalInstargetSize: number = target.length;
    target = target.concat(new Array<Inst>(numInsertions).fill(Inst.emptyInst()));
    let lastIndex: number = target.length;
    let indexInInsertions = numInsertions;
    while (indexInInsertions > 0) {
      indexInInsertions -= 1;
      let insertion = this._insertions[indexInInsertions];
      if (indexInInsertions !== 0 &&
        insertion.index < this._insertions[indexInInsertions - 1].index) {
        throw new Error('Insertions out of order');
      }
      if (insertion.index > originalInstargetSize) {
        throw new Error('Out-of-bounds insertion');
      }
      let firstIndex = insertion.index + indexInInsertions;
      let indexOffset = indexInInsertions + 1;
      let i = lastIndex - 1;
      while (i > firstIndex) {
        target[i] = target[i - indexOffset];
        i -= 1;
      }
      target[firstIndex] = insertion.element;
      lastIndex = firstIndex;
    }
    this._insertions = new Array();
    return numInsertions;
  }
}
